/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */


package learn.round1C;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Map;
import java.util.TreeMap;
import java.io.IOException;
import java.util.PriorityQueue;
import static chanlib.Chan_IO.*;
import static java.lang.Math.min;

/**
 * @author Expression author is undefined on line 16, column 14 in Templates/Classes/Class_1.java.
 */
public class MakingChessBoard{
    /*
      All neccesary to be defined
      including:
      variable, inner class
    */
    // static int A;
    // static void B();
    // static class C
    final static int bound=513;
    static class Board implements Comparable<Board>{
        int i,j,offset;
        int ipad;int jpad;
        Board(int i,int j, int offset){
            this.i=i;this.j=j;this.offset=offset;
            this.ipad=i+offset;this.jpad=j+offset;
        }

        @Override
        public java.lang.String toString() {
            return String.format("%d, %d, %d", i, j, offset);
        }

        @Override
        public int compareTo(Board o) {
            return o.offset-this.offset==0?(this.i-o.i==0?this.j-o.j:this.i-o.i):o.offset-this.offset;
        }
    }
    /*
       One calculation fits all of the cases.
    */
    static void preReckon(){
        return;
    }

    /*
      calculate the answer
    */
    private static void reckonSmall(int caseid) {
        int M=Int();
        int N=Int();
        int [][] bark=new int[bound][bound];        
        char c[] = new char[N/4];
        for(int i=0;i<M;i++){
            c=String().toCharArray();
            for(int j=0;j<N/4;j++){
                int k=Integer.valueOf(c[j]+"", 16);
                bark[i][4*j]=(k/8%2==1)?1:2;
                bark[i][4*j+1]=(k/4%2==1)?1:2;
                bark[i][4*j+2]=(k/2%2==1)?1:2;
                bark[i][4*j+3]=(k%2==1)?1:2;
            }
        }

        //TreeMap<Integer,Integer> count= new  TreeMap<Integer, Integer>(Collections.reverseOrder());
        //Board[] boards = new Board[M*N];
        ArrayList<Board> admited=new ArrayList<Board>();
        PriorityQueue<Board> waiting=new PriorityQueue<Board>();
        //int boardnums=0;

        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                // offset = margin from point (i,j) to valid bark boundary.
                int offset=0;
                if(bark[i][j]==0)continue;
                boolean valid=true;
                waiting.add(new Board(i, j, offset));
                do{
                    offset++;
                    for(int row=i;valid&&row<=i+offset;row++){
                        if(bark[row][j+offset-1]+bark[row][j+offset]!=3)valid=false;
                    }
                    for(int col=j;valid&&col<=j+offset;col++){
                        if(bark[i+offset-1][col]+bark[i+offset][col]!=3)valid=false;
                    }
                    if(bark[i+offset-1][j+offset-1]!=bark[i+offset][j+offset])valid=false;

                    if(valid)waiting.add(new Board(i, j, offset));
                }while(valid);
            }
        }

        // check for overlapping
check:      while(!waiting.isEmpty()){
            Board lowpri=waiting.poll();
            int i=lowpri.i,j=lowpri.j,ipad =lowpri.ipad,jpad=lowpri.jpad;
         
            for(Board highpri:admited){
                int i_=highpri.i,j_=highpri.j,ipad_ =highpri.ipad,jpad_=highpri.jpad;
                int hit=0;
                if(i_<=i&&i<=ipad_&&j_<=j&&j<=jpad_)hit|=1;
                if(i_<=i&&i<=ipad_&&j_<=jpad&&jpad<=jpad_)hit|=1;
                if(i_<=ipad&&ipad<=ipad_&&j_<=j&&j<=jpad_)hit|=1;
                if(i_<=ipad&&ipad<=ipad_&&j_<=jpad&&jpad<=jpad_)hit|=1;
                if(hit==1) continue check;
            }
            admited.add(lowpri);
        }
        TreeMap<Integer,Integer> counter=new TreeMap<Integer, Integer>(Collections.reverseOrder());
        for(Board m:admited){
            Integer boardSize=m.offset+1;
            Integer freq = counter.get(boardSize);
            counter.put(boardSize, (freq == null ? 1 : freq + 1));
        }
        writeln(String.format("Case #%d: %d",caseid,counter.size()), OUTFILE);
        println(String.format("Case #%d: %d",caseid,counter.size()));
        for(Map.Entry pair:counter.entrySet()){
            writeln(String.format("%d %d", pair.getKey(),pair.getValue()),OUTFILE);
            println(String.format("%d %d", pair.getKey(),pair.getValue()));
        }
    }
    private static void reckonLarge(int caseid) {
        int M=Int();
        int N=Int();
        int [][] bark=new int[bound][bound];
        int counter[]=new int[bound];
        char c[] = new char[N/4];
        for(int i=0;i<M;i++){
            c=String().toCharArray();
            for(int j=0;j<N/4;j++){
                int k=Integer.valueOf(c[j]+"", 16);
                bark[i][4*j]=(k/8%2==1)?1:-1;
                bark[i][4*j+1]=(k/4%2==1)?1:-1;
                bark[i][4*j+2]=(k/2%2==1)?1:-1;
                bark[i][4*j+3]=(k%2==1)?1:-1;
            }
        }

        //TreeMap<Integer,Integer> counter= new TreeMap<Integer, Integer>(Collections.reverseOrder());
        for(int size=bound;size>0;size--){
            indexing:
            for(int i=0;i<M;i++){
                if(i+size>M) break indexing;
                for(int j=0;j<N;j++){
                    if(j+size>N) break;
                    int offset_i=0,offset_j=0;
                    compare:
                    for(offset_i=0;offset_i<size;offset_i++)
                    for(offset_j=0;offset_j<size;offset_j++){
                        if(bark[i+offset_i][j+offset_j]==0) break compare;
                        else{
                            boolean parity=(offset_i+offset_j)%2==0;                            
                            if(bark[i+offset_i][j+offset_j]!=(parity?bark[i][j]:-bark[i][j]))break compare;
                        }
                    }
                    
                    if(offset_i==size&&offset_j==size){
                        //Integer freq=counter.get(size);
                        //counter.put(size, freq==null?1:freq+1);
                        counter[size]++;
                        for(offset_i=0 ;offset_i<size;offset_i++)
                        for(offset_j=0;offset_j<size;offset_j++)
                            bark[i+offset_i][j+offset_j]=0;
                    }
               }
           }
       }
       int countersize=0;
       for(int j=counter.length-1;j>=0;j--)if(counter[j]!=0)countersize++;
       writeln(String.format("Case #%d: %d",caseid,countersize),OUTFILE);

       for(int j=counter.length-1;j>=0;j--)if(counter[j]!=0){
            if(counter[j]!=0)
                writeln(String.format("%d %d", j,counter[j]), OUTFILE);
       }
    }

    static void reckonDynamicVer(int linenum){
        class Board implements Comparable{
        int size,i,j;

        public Board(int size,int i,int j) {
            this.size=size;this.i=i;this.j=j;
        }

        @Override
        public int compareTo(Object obj) {
//            if(this.size>o.size)return -1;
//            else if(this.size<o.size) return 1;
//            else if(this.i<o.i)return -1;
//            else if(this.i>o.i)return 1;
//            else if(this.j<o.j)return -1;
//            else if(this.j>o.j)return 1;
//            else return 0;
            Board o=(Board)obj;
            return this.size<o.size?1:this.size!=o.size?-1:this.i>o.i?1:this.i!=o.i?-1:this.j>o.j?1:this.j!=o.j?-1:0;
        }
    }
        int M=Int();
        int N=Int();
        boolean board[][]=new boolean[M][N];
        for(int i=0;i<M;i++){
            String row=String();
            for(int j=0;j<N/4;j++){
                int cells=Integer.valueOf(row.substring(j,j+1),16);
                board[i][4*j+3]=cells%2==1;cells/=2;
                board[i][4*j+2]=cells%2==1;cells/=2;
                board[i][4*j+1]=cells%2==1;cells/=2;
                board[i][4*j]=cells%2==1;cells/=2;
            }
        }
        int large[][]=new int[M][N];
        for(int i=0;i<M||i<N;i++){
           if(i<M) large[i][0]=1;
           if(i<N) large[0][i]=1;
        }
        boolean dependent[][]=new boolean[M][N];
        for(int i=1;i<M;i++)for(int j=1;j<N;j++)
           if(dependent[i][j]=board[i-1][j]!=board[i][j]&&
              board[i][j-1]!=board[i][j]&&
              board[i-1][j-1]==board[i][j]
              )large[i][j]=1+min(large[i-1][j],min(large[i][j-1],large[i-1][j-1]));
           else large[i][j]=1;

        PriorityQueue<Board> heap=new PriorityQueue<Board>();
        Board[][] pointer=new Board[M][N];
        for(int i=0;i<M;i++)for(int j=0;j<N;j++){
            heap.add(pointer[i][j]=new Board(large[i][j], i, j));
            //if(large[i][j]==0)println("xxx");
        }

        TreeMap<Integer,Integer> counter = new TreeMap<Integer, Integer>(Collections.reverseOrder());
        while(!heap.isEmpty()){
            Board largest=heap.poll();
            Integer freq=counter.get(largest.size);
            counter.put(largest.size, (freq==null)?1:freq+1);
            // increment the counter for the size of largest
            int lowI=largest.i-largest.size+1,highI=min(largest.i+largest.size,M-1);
            int lowJ=largest.j-largest.size+1,highJ=min(largest.j+largest.size,N-1);
            int centerI=largest.i,centerJ=largest.j;
            for(int i=lowI;i<=highI;i++){
            for(int j=lowJ;j<=highJ;j++){
                    if(i<=centerI&&j<=centerJ){
                        large[i][j]=0;
                        heap.remove(pointer[i][j]);
                        //pointer[i][j].size=large[i][j]; worth nothing as it will be no longer inserted into the heap.
                    }else{
                            if(dependent[i][j]){
                                if(heap.remove(pointer[i][j])){
                                large[i][j]=1+min(large[i-1][j],min(large[i][j-1],large[i-1][j-1]));
                                pointer[i][j].size=large[i][j];
                                 heap.add(pointer[i][j]);
                                }
                            }
                    }
                }
            }
        }
        writeln(String.format("Case #%d: %d",linenum,counter.size()), OUTFILE);
        println(String.format("%d",linenum));
        for(Map.Entry<Integer,Integer> pair:counter.entrySet())
            writeln(String.format("%d %d", pair.getKey(),pair.getValue()), OUTFILE);
        // print out put here: with linenum taken into account
    }
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        /*
           Pre-computing for all cases
        */

        // Just in case!
        //preReckon();
        //while((char)read()!='P');

        /*
          Input-output
        */
        boolean test=false;
        boolean small=false;
        String prob="C";
        String filename;
        if(test) filename="test";
        else{
            if(small) filename=prob+"-small-practice";
            else filename=prob+"-large-practice";
        }
        try {
            /*
               Init IO,plus determination of input line number
             */
            int lineNums = initFileIO(filename);
            for (int i = 1; i <= lineNums; i++) {
                reckonLarge(i);
            }
        } finally {
            endIO();
        }
    }

}
